package fun.coding.baozi.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import fun.coding.leetcode.TreeNode;

public class BinaryTreeHelper {
	
	public static void main(String[] args) {
		/*
		 *         1 
		 *     2         4
		 *   #   3    6     #
		 *      # #  # 8
		 *      
		 *   1 2 4 # 3 6 # # # # 8      
	 	 */
		String[] test1 = {"1", "2", "4", "#", "3", "6", "#", "#", "#", "#", "8"};
		TreeNode root1 = BinaryTreeHelper.deserializeBinaryTree(Arrays.asList(test1));
		List<String> test1Actual = BinaryTreeHelper.serializeBinaryTree(root1);
		assert test1Actual.equals(Arrays.asList(test1));
		
		/*
		 *                     1
		 *                   2   #
		 *                 3   
		 */
		String[] test2 = {"1", "2", "#", "3"};
		TreeNode root2 = BinaryTreeHelper.deserializeBinaryTree(Arrays.asList(test2));
		List<String> test2Actual = BinaryTreeHelper.serializeBinaryTree(root2);
		assert test2Actual.equals(Arrays.asList(test2));
		
		/*
		 *                        1
		 *                    #        2
		 *                          4      3  
		 *                         #  #  5
		 *   5 is left child of 3
		 *   1, #, 2, 4, 3, #, #, 5
		 */
		String[] test3 = {"1", "#", "2", "4", "3", "#", "#", "5"};
		TreeNode root3 = BinaryTreeHelper.deserializeBinaryTree(Arrays.asList(test3));
		List<String> test3Actual = BinaryTreeHelper.serializeBinaryTree(root3);
		assert test3Actual.equals(Arrays.asList(test3));
		
		String[] test4 = {"1"};
		TreeNode root4 = BinaryTreeHelper.deserializeBinaryTree(Arrays.asList(test4));
		List<String> test4Actual = BinaryTreeHelper.serializeBinaryTree(root4);
		assert test4Actual.equals(Arrays.asList(test4));
		
	}
	
	/**
	 * Serialize a binary tree, use # as place holder
	 * @param root
	 * @return Use string here since we cannot use any integer value as place holder
	 */
	public static List<String> serializeBinaryTree(TreeNode root) {
		List<String> res = new ArrayList<String>();
		
		if (root == null) return res;
		
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.add(root);
		
		while (!q.isEmpty()) {
			for (int i = 0; i < q.size(); i++) {
				TreeNode t = q.poll();
				if (t == null) {
					res.add("#");
					continue;
				}
				
				res.add(String.valueOf(t.val));
				q.add(t.left);
				q.add(t.right);
			}
		}
		
		// trim all the tailing #s
		for (int i = res.size() - 1; i >= 0; i--) {
			if (res.get(i) != "#") {
				break;
			} 
			res.remove(i);
		}
		return res;
	}
	

	public static TreeNode deserializeBinaryTree(List<String> l) {
		if (l == null || l.size() == 0) return null;
		
		int i = 0;
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
		q.add(root);
		int size = l.size();
		
		while (!q.isEmpty() && i < size) {
			TreeNode cur = q.poll();
			
			if ((i + 1) < size) {
				String leftStr = l.get(i + 1);
				if (leftStr != "#") {
					TreeNode leftNode = new TreeNode(Integer.valueOf(leftStr)); 
					cur.left = leftNode;
					q.add(leftNode);
				}
				i++;
			}
			
			if ((i + 1) < size) {
				String rightStr = l.get(i + 1);
				if (rightStr != "#") {
					TreeNode rightNode = new TreeNode(Integer.valueOf(rightStr));
					cur.right = rightNode;
					q.add(rightNode);
				}
				i++;
			}
			
		}
		return root;
	}
}
